package com.ifish.leetcode.problem.algorithm;

import com.ifish.leetcode.problem.BaseLeetCodeProblem;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by iFish on 2017/7/8.
 */

public class _0003 extends BaseLeetCodeProblem {

    @Override
    public String title() {
        return "Longest Substring Without Repeating Characters ";
    }

    @Override
    public int difficulty() {
        return 1;
    }

    @Override
    public void run() {
        super.run();

        String test = "abcd";
        int l = lengthOfLongestSubstring(test);
        printResult("longest substring length: " + l);
    }

    public int lengthOfLongestSubstring(String s) {
        int curLong = 0;
        List collectList = new ArrayList();
        char []strArr = s.toCharArray();
        for (int i = 0; i < strArr.length; i++) {
            int index = collectList.indexOf(strArr[i]);
            if (index != -1) {
                // 已收集的串是最长，更新最长记录
                if (collectList.size() > curLong) {
                    curLong = collectList.size();
                }
                for (int j = 0; j <= index; j++) {
                    collectList.remove(0);
                }
            }
            collectList.add(strArr[i]);
            // 最后再更新一次
            if (i == strArr.length - 1 && collectList.size() > curLong) {
                curLong = collectList.size();
            }
        }
        return curLong;
    }

    /**
     * Sliding window
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            // 记录应该从i开始计算子串的index
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            // 更新该字符的索引（保证索引代表该字符出现的最远位置）
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}
